package com.zjsru.studyplan1;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 图像渲染
 * <p>
 * 输入:
 * image = [[1,1,1],[1,1,0],[1,0,1]]
 * sr = 1, sc = 1, newColor = 2
 * 输出: [[2,2,2],[2,2,0],[2,0,1]]
 * 解析:
 * 在图像的正中间，(坐标(sr,sc)=(1,1)),
 * 在路径上所有符合条件的像素点的颜色都被更改成2。
 * 注意，右下角的像素没有更改为2，
 * 因为它不是在上下左右四个方向上与初始点相连的像素点。
 */
public class floodFill {
    int[] dx = {1, 0, 0, -1};
    int[] dy = {0, 1, -1, 0};

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        //广度优先搜索
        int currColor = image[sr][sc];
        if (currColor == newColor) {
            return image;
        }
        int n = image.length, m = image[0].length;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{sr, sc});
        image[sr][sc] = newColor;
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1];
            for (int i = 0; i < 4; i++) {
                int mx = x + dx[i], my = y + dy[i];
                if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor) {
                    queue.offer(new int[]{mx, my});
                    image[mx][my] = newColor;
                }
            }
        }
        return image;
    }

    public static void main(String[] args) {
        floodFill floodFill = new floodFill();
        int[][] image = new int[][]{{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
        int sr = 2;
        int sc = 2;
        int newColor = 2;
        System.out.println(floodFill.floodFill(image, sr, sc, newColor));
    }
//    递归
//    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
//
//        int a = image[sr][sc];
//        if (a != newColor) {
//            change(image, sr, sc, a, newColor);
//        }
//        return image;
//    }
//
//    private void change(int[][] image, int i, int j, int a, int newColor) {
//        if (i < 0 || i == image.length || j < 0 || j == image[0].length || image[i][j] != a) {
//            return;
//        }
//        image[i][j] = newColor;
//        change(image, i + 1, j, a, newColor);
//        change(image, i - 1, j, a, newColor);
//        change(image, i, j + 1, a, newColor);
//        change(image, i, j - 1, a, newColor);
//    }


//    深度优先搜索
//    int[] dx = {1, 0, 0, -1};
//    int[] dy = {0, 1, -1, 0};
//    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
//        int currColor = image[sr][sc];
//        if (currColor != newColor) {
//            dfs(image, sr, sc, currColor, newColor);
//        }
//        return image;
//    }
//
//    public void dfs(int[][] image, int x, int y, int color, int newColor) {
//        if (image[x][y] == color) {
//            image[x][y] = newColor;
//            for (int i = 0; i < 4; i++) {//上下左右四个方向
//                int mx = x + dx[i], my = y + dy[i];
//                if (mx >= 0 && mx < image.length && my >= 0 && my < image[0].length) {
//                    dfs(image, mx, my, color, newColor);
//                }
//            }
//        }
//    }

}
